Fix PR 22541: When values are equal, minmax should return the rightmost one in the initializer_list git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@228839 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/algorithm b/include/algorithm index 475ba66..415059d 100644 --- a/include/algorithm +++ b/include/algorithm
@@ -2771,7 +2771,7 @@ typedef typename initializer_list<_Tp>::const_iterator _Iter; _Iter __first = __t.begin(); _Iter __last = __t.end(); - std::pair<_Tp, _Tp> __result ( *__first, *__first ); + std::pair<_Tp, _Tp> __result(*__first, *__first); ++__first; if (__t.size() % 2 == 0) @@ -2786,13 +2786,13 @@ while (__first != __last) { _Tp __prev = *__first++; - if (__comp(__prev, *__first)) { - if (__comp(__prev, __result.first)) __result.first = __prev; - if (__comp(__result.second, *__first)) __result.second = *__first; + if (__comp(*__first, __prev)) { + if ( __comp(*__first, __result.first)) __result.first = *__first; + if (!__comp(__prev, __result.second)) __result.second = __prev; } else { - if (__comp(*__first, __result.first)) __result.first = *__first; - if (__comp(__result.second, __prev)) __result.second = __prev; + if ( __comp(__prev, __result.first)) __result.first = __prev; + if (!__comp(*__first, __result.second)) __result.second = *__first; } __first++; diff --git a/test/std/algorithms/alg.sorting/alg.min.max/minmax_init_list_comp.pass.cpp b/test/std/algorithms/alg.sorting/alg.min.max/minmax_init_list_comp.pass.cpp index 95a8c85..beae3b6 100644 --- a/test/std/algorithms/alg.sorting/alg.min.max/minmax_init_list_comp.pass.cpp +++ b/test/std/algorithms/alg.sorting/alg.min.max/minmax_init_list_comp.pass.cpp
@@ -12,11 +12,27 @@ // template<class T, class Compare> // pair<T, T> // minmax(initializer_list<T> t, Compare comp); +// +// Complexity: At most (3/2) * t.size() applications of the corresponding predicate. #include <algorithm> #include <functional> #include <cassert> +#include "counting_predicates.hpp" + +bool all_equal(int a, int b) { return false; } // everything is equal + +void test_all_equal(std::initializer_list<int> il) +{ + binary_counting_predicate<bool(*)(int, int), int, int> pred (all_equal); + std::pair<int, int> p = std::minmax(il, std::ref(pred)); + const int *ptr = il.end(); + assert(p.first == *il.begin()); + assert(p.second == *--ptr); + assert(pred.count() <= ((3 * il.size()) / 2)); +} + int main() { #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS @@ -26,6 +42,25 @@ assert((std::minmax({2, 3, 1}, std::greater<int>()) == std::pair<int, int>(3, 1))); assert((std::minmax({3, 1, 2}, std::greater<int>()) == std::pair<int, int>(3, 1))); assert((std::minmax({3, 2, 1}, std::greater<int>()) == std::pair<int, int>(3, 1))); + assert((std::minmax({1, 2, 3}, all_equal ) == std::pair<int, int>(1, 3))); + + binary_counting_predicate<std::greater<int>, int, int> pred ((std::greater<int>())); + assert((std::minmax({1, 2, 2, 3, 3, 3, 5, 5, 5, 5, 5, 3}, std::ref(pred)) == std::pair<int, int>(5, 1))); + assert(pred.count() <= 18); // size == 12 + + test_all_equal({0}); + test_all_equal({0,1}); + test_all_equal({0,1,2}); + test_all_equal({0,1,2,3}); + test_all_equal({0,1,2,3,4}); + test_all_equal({0,1,2,3,4,5}); + test_all_equal({0,1,2,3,4,5,6}); + test_all_equal({0,1,2,3,4,5,6,7}); + test_all_equal({0,1,2,3,4,5,6,7,8}); + test_all_equal({0,1,2,3,4,5,6,7,8,9}); + test_all_equal({0,1,2,3,4,5,6,7,8,9,10}); + test_all_equal({0,1,2,3,4,5,6,7,8,9,10,11}); + #if _LIBCPP_STD_VER > 11 { static_assert((std::minmax({1, 2, 3}, std::greater<int>()) == std::pair<int, int>(3, 1)), ""); 